import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;






class Student implements Comparable<Student>{
    public int age;
    public String name;

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

    //只是比较对象的大小关系，返回值有整数 0 负数
    @Override
    public int compareTo(Student o) {
        //return this.age - o.age;//小根堆比较方式
        return o.age - this.age;
    }

    //比较是否相等，返回值是true 或者是 false
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age;
    }

    @Override
    public int hashCode() {
        return Objects.hash(age);
    }
}

class AgeComparator implements Comparator<Student> {

    //年龄比较器
    @Override
    public int compare(Student o1, Student o2) {
        return o2.age - o1.age;
    }
}
class NameComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.name.compareTo(o2.name);
    }
}


    class Imp implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }
public class Test {

    /**
     * Created with IntelliJ IDEA.
     * Description:测试自己实现的堆排序
     * User: 牛孟俊
     * Date: 2023-10-19
     * Time: 15：58
     */

    public static void main(String[] args) {
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue();
        int[] array = {10,30,25,0,24,82,3,64};
        myPriorityQueue.createHeap(array);
        myPriorityQueue.pollHeap();
        System.out.println("====================");
    }


    //时间复杂度 最坏情况下O(N^2)
    //最好情况下O(N), 有序的情况下 --------- 插入排序 当数据越有序的时候 越快

    //使用场景：数据越有序的时候采用插入排序
    //空间复杂多O(1)
    //插入排序
    /*public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//存放i下标的值
            int j = i-1;
            for(; j >= 0; j--) {
                if(array[j] < tmp) {
                    array[j+1] = array[j];
                } else{
                 //array[j+1] = tmp
                    //到这里跳出循环了，执行一次array[j+1] = tmp,所以这里就可以省略
                 break;//说明i下标这个元素一级调整完了
                }
            }
            //说明现在已经 j < 0
            array[j+1] = tmp;
        }
*/






    /*//面试级别的topK解决方法
    public static int[] smallestK(int[] array,int k) {

        //存放最小的K个元素的数组
        int[] ret = new int[k];

        //创建大根堆
        //需要自定义一个比较器
        PriorityQueue<Integer> maxHape = new PriorityQueue<>(new Imp());
        for (int i = 0; i < k; i++) {
            //k个元素入堆
            maxHape.offer(array[i]);
        }
        //开始与第K+1个元素比较大小
        for(int i = k; i < array.length; i++) {
            int top = maxHape.peek();
            //比堆顶元素小的才入堆
            if(array[i] < top) {
                maxHape.poll();//弹出堆顶元素
                maxHape.offer(array[i]);
            }
        }

        //最小的K个元素已经入堆了
        //存放到数组当中
        for (int i = 0; i < k; i++) {
            //k个元素入堆
            ret[i] = maxHape.poll();
        }
        return ret;
    }


    //topK问题
    public static int[] smallestK1(int[] array,int k) {
        //这个代码不是真正的top K 的解决方法

      //找到前K个最小的数据
        PriorityQueue<Integer> minHape = new PriorityQueue<>();
        for(int x : array) {
            minHape.offer(x);
        }
        //小根堆当中已经把数据放进去了

        //这个方法的整体时间复杂度是k*logn + n

        //将前k个数放到一个数组当中
        int[] ret = new int[k];//动态初始化
        for(int i =0; i < k; i++) {
            ret[i] = minHape.poll();
        }
        //前k个数已经放入完成了
        return ret;
    }
    public static void main5(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "zhangsan";
        Student s2 = new Student();
        s2.age = 9;
        s2.name = "zhangsan";

        //传一个比较器给PPriorityQueue，就可以了
        AgeComparator ageComparator = new AgeComparator();
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>(ageComparator);
        priorityQueue.offer(s2);

        priorityQueue.offer(s1);

        Student ret = priorityQueue.poll();
        System.out.println(ret);
    }
    public static void main4(String[] args) {
        PriorityQueue<Integer> priprityQueue1 = new PriorityQueue<>();
        priprityQueue1.offer(11);
        priprityQueue1.offer(2);
        priprityQueue1.offer(3);
    }

    public static void main3(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "zhangsan";
        Student s2 = new Student();
        s2.age = 9;
        s2.name = "zhangsan";

        AgeComparator ageComparator = new AgeComparator();
        System.out.println(ageComparator.compare(s1, s2));

        NameComparator nameComparator = new NameComparator();
        System.out.println(nameComparator.compare(s1, s2));
    }
    public static void main2(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "zhangsan";
        Student s2 = new Student();
        s2.age = 9;
        s2.name = "zhangsan";

        System.out.println(s1.equals(s2));


        System.out.println(s1.compareTo(s2));
    }


    public static void main1(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        //使用Queue，PriorityQueue这个类实现了Queue这个接口
        //默认分配了一个长度为11的数组
        Queue<Integer> priprityQueue1 = new PriorityQueue<>();
        priprityQueue1.offer(1);
        priprityQueue1.offer(2);
        priprityQueue1.offer(3);
        priprityQueue1.offer(4);

        System.out.println(priprityQueue1.poll());
        System.out.println(priprityQueue1.poll());
        System.out.println(priprityQueue1.poll());
        System.out.println(priprityQueue1.poll());

        Queue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student());//插入第一个自定义类型时可以运行
        priorityQueue2.offer(new Student());//插入第二个自定义类型会报错
        //如果想不报错，那么就需要将这个强制类型转换

        //priorityQueue2.offer(null);

    }

    *//**
     * 比较器
     * o2 - o1 大根堆
     * o1 - o2 小根堆
     * *//*
class Imp1 implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 -o1;
        }
    }
    *//**
     *最小前K个数
     *解题思路
     * 1.建立容量为K的大根堆
     * 2.从第K+1个数与堆顶元素比较
     * 3.比堆顶元素小的就放到堆当中
    * *//*
    public int[] smallestK(int[] array, int k) {
        int[] ret = new int[k];
        if(k == 0) return ret;
        PriorityQueue<Integer> maxHape = new PriorityQueue(k,new Imp());//优先级队列是小根堆，所以需要使用比较器
        for(int i = 0; i < k; i++) {
            maxHape.offer(array[i]);
        }
        //2.从第K+1个数与堆顶元素比较
        for (int i = k; i < array.length; i++) {
            int top = maxHape.peek();
            if(array[i] < top) {
                maxHape.poll();
                maxHape.offer(array[i]);
            }
        }
        //放到数组当中
        for(int i = 0; i < k;i++) {
            ret[i] = maxHape.poll();
        }
        return ret;
    }*/
}
